class Node{
    //children
    //link
    constructor(owner){
        this.owner=owner;
        this.keys=[];
        this.children=null;
    }

    insert(value){
        let up;
        let comp=this.owner.comparator;
        let pos=this.keys.length;
        for (let i=0;i<this.keys.length;++i){
            if (comp.gt(this.keys[i],value)){
                pos=i;
                break;
            }
        }
        if (this.children){
            up=this.children[pos].insert(value);
            if (up===true) return true;
            this.children.splice(pos,1,...up.children);
            this.keys.splice(pos,0,up.value);
        }else{
            this.keys.splice(pos,0,value);
        }
        if (this.keys.length>this.owner.maxKeyCount){
            let left=new Node(this.owner);
            let right=new Node(this.owner);
            let i=parseInt(this.keys.length/2);
            left.keys=this.keys.slice(0,i);
            right.keys=this.keys.slice(i+1);
            if (this.children){
                left.children=this.children.slice(0,i+1);
                right.children=this.children.slice(i+1);
            }
            return {
                value:this.keys[i],
                children:[left,right]
            }
        }else{
            return true;
        }
    }

    query(gtMin,ltMax,cb,depth){
        console.log("*".repeat(depth),this.keys);
        for (let i=0;i<this.keys.length;++i){
            let val=this.keys[i];
            //if (!ltMax(val)) break;
            if (gtMin(val)){
                if (this.children) {
                    this.children[i].query(gtMin, ltMax,cb, depth + 1);
                }
                if (!ltMax(val)) break;
                cb(this.keys[i], depth, this, i)
            }
        }
        let val=this.keys[this.keys.length-1];
        if (this.children&&ltMax(val)) {
            this.children[this.keys.length].query(gtMin, ltMax,cb, depth + 1);
        }
    }

    erase(gtMin,ltMax){
        let out=[];
    }

    visit(cb,depth){
        for (let i=0;i<this.keys.length;++i){
            if (this.children) this.children[i].visit(cb,depth+1);
            cb(this.keys[i],depth,this,i)
        }
        if (this.children) this.children[this.keys.length].visit(cb,depth+1);
    }
}

export default class BTree{
    comparator=(a,b)=>a<b;
    maxKeyCount=4;
    unique=false;

    constructor(comp){
        this.root=new Node(this);
        if (comp) this.comparator=comp;
        else comp=this.comparator;
        this.comparator.lt=(l,r)=>comp(l,r);
        this.comparator.gt=(l,r)=>comp(r,l);
        this.comparator.le=(l,r)=>!comp(r,l);
        this.comparator.ge=(l,r)=>!comp(l,r);
        this.comparator.eq=(l,r)=>!comp(l,r)&&!comp(r,l);
    }
    insert(value){
        let up=this.root.insert(value);
        if (up===true) return true;
        this.root=new Node(this);
        this.root.keys=[up.value];
        this.root.children=up.children;
        return true;
    }

    query(gtMin,ltMax,cb){
        let out=[];
        if (cb==null) cb=(v,_,n,i)=>out.push({v,n,i});
        this.root.query(gtMin,ltMax,cb,0);
        return out;
    }

    visit(cb){
        this.root.visit(cb,0);
    }

    remove(){
        throw Error("not implement")
    }
}